import java.util.List;

public class Hanota {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        // 将 A 中所有盘子, 借助 B 移动到 C 上
        dfs(A, B, C, A.size());
    }

    public void dfs(List<Integer> A, List<Integer> B, List<Integer> C, int n) {
        if(n == 1) {
            // 当只有一个盘子时, 把 A 顶端盘子(只有一个盘子)移动到 C 上
            C.add(A.remove(A.size()-1));
            return;
        }
        // 1.将 A 中的 n-1 个盘子, 借助 C 移动到 B 上
        dfs(A, C, B, n - 1);
        // 2.移动盘子操作,可以理解为将 A 最后一个盘子移动到 C 上
        C.add(A.remove(A.size() - 1));
        // 3.将 B 中的 n-1 个盘子, 借助 A 移动到 C 上
        dfs(B, A, C, n-1);
    }
}
